{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "############## PLEASE RUN THIS CELL FIRST! ###################\n",
    "\n",
    "# import everything and define a test runner function\n",
    "from importlib import reload\n",
    "from helper import run\n",
    "import ecc\n",
    "import helper\n",
    "\n",
    "from ecc import FieldElement, Point"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exercise 1\n",
    "\n",
    "Evaluate whether these points are on the curve \\\\(y^{2}\\\\)=\\\\(x^{3}\\\\)+7 over \\\\(F_{223}\\\\)\n",
    "\n",
    "(192,105), (17,56), (200,119), (1,193), (42,99)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Exercise 1\n",
    "\n",
    "prime = 223\n",
    "a = FieldElement(0, prime)\n",
    "b = FieldElement(7, prime)\n",
    "\n",
    "# (192,105), (17,56), (200,119), (1,193), (42,99)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from ecc import FieldElement, Point\n",
    "a = FieldElement(num=0, prime=223)\n",
    "b = FieldElement(num=7, prime=223)\n",
    "x = FieldElement(num=192, prime=223)\n",
    "y = FieldElement(num=105, prime=223)\n",
    "p1 = Point(x, y, a, b)\n",
    "print(p1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from ecc import FieldElement, Point\n",
    "prime = 223\n",
    "a = FieldElement(num=0, prime=prime)\n",
    "b = FieldElement(num=7, prime=prime)\n",
    "x1 = FieldElement(num=192, prime=prime)\n",
    "y1 = FieldElement(num=105, prime=prime)\n",
    "x2 = FieldElement(num=17, prime=prime)\n",
    "y2 = FieldElement(num=56, prime=prime)\n",
    "p1 = Point(x1, y1, a, b)\n",
    "p2 = Point(x2, y2, a, b)\n",
    "print(p1+p2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exercise 2\n",
    "\n",
    "For the curve \\\\(y^{2}\\\\)=\\\\(x^{3}\\\\)+7 over \\\\(F_{223}\\\\), find:\n",
    "\n",
    "* (170,142) + (60,139)\n",
    "* (47,71) + (17,56)\n",
    "* (143,98) + (76,66)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Exercise 2\n",
    "\n",
    "prime = 223\n",
    "a = FieldElement(0, prime)\n",
    "b = FieldElement(7, prime)\n",
    "\n",
    "# (170,142) + (60,139)\n",
    "# (47,71) + (17,56)\n",
    "# (143,98) + (76,66)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exercise 3\n",
    "\n",
    "Extend `ECCTest` to test for the additions from the previous exercise. Call this `test_add`.\n",
    "\n",
    "#### Make [this test](/edit/code-ch03/ecc.py) pass: `ecc.py:ECCTest:test_add`"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Exercise 3\n",
    "\n",
    "reload(ecc)\n",
    "run(ecc.ECCTest(\"test_add\"))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exercise 4\n",
    "\n",
    "For the curve \\\\(y^{2}\\\\)=\\\\(x^{3}\\\\)+7 over \\\\(F_{223}\\\\), find:\n",
    "\n",
    "* 2⋅(192,105)\n",
    "* 2⋅(143,98)\n",
    "* 2⋅(47,71)\n",
    "* 4⋅(47,71)\n",
    "* 8⋅(47,71)\n",
    "* 21⋅(47,71)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Exercise 4\n",
    "\n",
    "prime = 223\n",
    "a = FieldElement(0, prime)\n",
    "b = FieldElement(7, prime)\n",
    "\n",
    "# 2*(192, 105)\n",
    "# 2*(143, 98)\n",
    "# 2*(47, 71)\n",
    "# 4*(47, 71)\n",
    "# 8*(47, 71)\n",
    "# 21*(47, 71)\n",
    "\n",
    "# create a product variable\n",
    "# add the point to the product n times\n",
    "# print the product"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from ecc import FieldElement, Point\n",
    "prime = 223\n",
    "a = FieldElement(0, prime)\n",
    "b = FieldElement(7, prime)\n",
    "x = FieldElement(47, prime)\n",
    "y = FieldElement(71, prime)\n",
    "p = Point(x, y, a, b)\n",
    "for s in range(1,21):\n",
    "    result = s*p\n",
    "    print('{}*(47,71)=({},{})'.format(s,result.x.num,result.y.num))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exercise 5\n",
    "\n",
    "For the curve \\\\(y^{2}\\\\)=\\\\(x^{3}\\\\)+7 over \\\\(F_{223}\\\\), find the order of the group generated by (15,86)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Exercise 5\n",
    "\n",
    "prime = 223\n",
    "a = FieldElement(0, prime)\n",
    "b = FieldElement(7, prime)\n",
    "x = FieldElement(15, prime)\n",
    "y = FieldElement(86, prime)\n",
    "p = Point(x, y, a, b)\n",
    "inf = Point(None, None, a, b)\n",
    "\n",
    "# create a product variable\n",
    "# create a counter variable\n",
    "# loop until the product is the point at infinity\n",
    "# add the point to the product and increment counter\n",
    "# print the counter when exited from loop"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from ecc import FieldElement, Point\n",
    "prime = 223\n",
    "a = FieldElement(0, prime)\n",
    "b = FieldElement(7, prime)\n",
    "x = FieldElement(15, prime)\n",
    "y = FieldElement(86, prime)\n",
    "p = Point(x, y, a, b)\n",
    "print(7*p)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "gx = 0x79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798\n",
    "gy = 0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8\n",
    "p = 2**256 - 2**32 - 977\n",
    "print(gy**2 % p == (gx**3 + 7) % p)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from ecc import FieldElement, Point\n",
    "gx = 0x79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798\n",
    "gy = 0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8\n",
    "p = 2**256 - 2**32 - 977\n",
    "n = 0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141\n",
    "x = FieldElement(gx, p)\n",
    "y = FieldElement(gy, p)\n",
    "seven = FieldElement(7, p)\n",
    "zero = FieldElement(0, p)\n",
    "G = Point(x, y, zero, seven)\n",
    "print(n*G)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from ecc import G, N\n",
    "print(N*G)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from ecc import S256Point, G, N\n",
    "z = 0xbc62d4b80d9e36da29c16c5d4d9f11731f36052c72401a76c23c0fb5a9b74423\n",
    "r = 0x37206a0610995c58074999cb9767b87af4c4978db68c06e8e6e81d282047a7c6\n",
    "s = 0x8ca63759c1157ebeaec0d03cecca119fc9a75bf8e6d0fa65c841c8e2738cdaec\n",
    "px = 0x04519fac3d910ca7e7138f7013706f619fa8f033e6ec6e09370ea38cee6a7574\n",
    "py = 0x82b51eab8c27c66e26c858a079bcdf4f1ada34cec420cafc7eac1a42216fb6c4\n",
    "point = S256Point(px, py)\n",
    "s_inv = pow(s, N-2, N)\n",
    "u = z * s_inv % N\n",
    "v = r * s_inv % N\n",
    "print((u*G + v*point).x.num == r)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exercise 6\n",
    "\n",
    "Verify whether these signatures are valid:\n",
    "\n",
    "```\n",
    "P = (0x887387e452b8eacc4acfde10d9aaf7f6d9a0f975aabb10d006e4da568744d06c,\n",
    "0x61de6d95231cd89026e286df3b6ae4a894a3378e393e93a0f45b666329a0ae34)\n",
    "\n",
    "# signature 1\n",
    "z = 0xec208baa0fc1c19f708a9ca96fdeff3ac3f230bb4a7ba4aede4942ad003c0f60\n",
    "r = 0xac8d1c87e51d0d441be8b3dd5b05c8795b48875dffe00b7ffcfac23010d3a395\n",
    "s = 0x68342ceff8935ededd102dd876ffd6ba72d6a427a3edb13d26eb0781cb423c4\n",
    "\n",
    "# signature 2\n",
    "z = 0x7c076ff316692a3d7eb3c3bb0f8b1488cf72e1afcd929e29307032997a838a3d\n",
    "r = 0xeff69ef2b1bd93a66ed5219add4fb51e11a840f404876325a1e8ffe0529a2c\n",
    "s = 0xc7207fee197d27c618aea621406f6bf5ef6fca38681d82b2f06fddbdce6feab6\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Exercise 6\n",
    "\n",
    "point = S256Point(\n",
    "    0x887387e452b8eacc4acfde10d9aaf7f6d9a0f975aabb10d006e4da568744d06c, \n",
    "    0x61de6d95231cd89026e286df3b6ae4a894a3378e393e93a0f45b666329a0ae34)\n",
    "# signature 1\n",
    "z = 0xec208baa0fc1c19f708a9ca96fdeff3ac3f230bb4a7ba4aede4942ad003c0f60\n",
    "r = 0xac8d1c87e51d0d441be8b3dd5b05c8795b48875dffe00b7ffcfac23010d3a395\n",
    "s = 0x68342ceff8935ededd102dd876ffd6ba72d6a427a3edb13d26eb0781cb423c4\n",
    "# signature 2\n",
    "z = 0x7c076ff316692a3d7eb3c3bb0f8b1488cf72e1afcd929e29307032997a838a3d\n",
    "r = 0xeff69ef2b1bd93a66ed5219add4fb51e11a840f404876325a1e8ffe0529a2c\n",
    "s = 0xc7207fee197d27c618aea621406f6bf5ef6fca38681d82b2f06fddbdce6feab6"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from ecc import S256Point, G, N\n",
    "from helper import hash256\n",
    "e = int.from_bytes(hash256(b'my secret'), 'big')\n",
    "z = int.from_bytes(hash256(b'my message'), 'big')\n",
    "k = 1234567890\n",
    "r = (k*G).x.num\n",
    "k_inv = pow(k, N-2, N)\n",
    "s = (z+r*e) * k_inv % N\n",
    "point = e*G\n",
    "print(point)\n",
    "print(hex(z))\n",
    "print(hex(r))\n",
    "print(hex(s))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exercise 7\n",
    "\n",
    "Sign the following message with the secret\n",
    "\n",
    "```\n",
    "e = 12345\n",
    "z = int.from_bytes(hash256('Programming Bitcoin!'), 'big')\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Exercise 7\n",
    "\n",
    "# Exercise 7\n",
    "\n",
    "e = 12345\n",
    "z = int.from_bytes(hash256(b'Programming Bitcoin!'), 'big')\n",
    "\n",
    "# choose a random k\n",
    "# calculate r (kG's x-coordinate)\n",
    "# calculate s ((z+re)/k)\n",
    "# print the point, z, r and s"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
